COMMENT ⊗   VALID 00005 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	Possible games
C00003 00003	Games requiring a stored vocabulary
C00011 00004	Text storage with data compression
C00018 00005	Penny matching
C00020 ENDMK
C⊗;
Possible games

1)  Reversie (Othello)
2)  Kalah
3)  3-dimensional Tic Tac Toe
4)  Master-mind
5)  Nine men's Morris (Muhle, Marelle, The Mill or Merry Peg)
6)  Hex
7)  Battleship
8)  Matching pennies
9)  Scrabble
10) Sprouts
11) Backgammon
12) Chinese Checkers (so called)
13) Go Moku
14) Checker monitor
15) Bingo
16) Parcheesi
17) Chess
18) Chess monitor
19) Go
20) Nim
Games requiring a stored vocabulary

It would be nice to be able to have the computer act as a referee for word
games and also to allow a single player to play against the machine.   All
such games would require a stored vocabulary.

There are three basic techniques  for minimizing the storage  requirements
of such a vocabulary, 1) Hashing 2) Tree storage and 3) An exploitation of
the inherent structure of English by the use of Huffman coding techniques.

1) Hashing.  Floyd has studied the hashing technique and seems to favor it
for small machines.  However it is not  error free and it makes no use  of
any inherent order  in the  corpus.  It  is undoubtedly  superior for  the
storage of completely general vocabularies but probably not as good as the
tree method for vocabularies in which only short words are allowed.

2) Tree storage. This  technique works best for  ordered data with a  high
degree of structure and  seems to be admirably  suited to vocabularies  in
which the word  size is limited.   This scheme will  be described in  more
detail below.

3) Huffman  coding.  This  technique  probably take  too much  coding  and
decoding effort  to  be of  much  use  for small  vocabularies  and  small
machines.

What follows is  a brief description  of one form  of tree structure  that
seems well suited for our needs.  To make it easy to understand, only  one
specific implimentation is described.  A study should certainly be made of
severial varients of this scheme before its actual implimentation.

The left  3  bits of  each  byte would  contain  a number  specifying  the
character position in  a word of  the character that  is contained in  the
last 5 bits of the byte.  In this way, only 1 byte is used to specify  the
first character  of  all  words  that  begin  with  any  given  character.
Similarly, if there are  2 or more  words with the  first 2 characters  in
common, then only one more  byte is used to  specify the second letter  of
these words.   The  same economy  in  bytes continues  for  all  character
positions in the words.

Unfortunately, one could not  store the characters in  the form needed  to
display them, as this requires 6 bits, but a 26-byte table would take care
of the conversion if only letters were to be allowed.

In the example shown below, the average  number of bytes per word is  2.1.
This number depends upon the character  of the vocabulary, and it is  less
if multiple endings are  shown for all root  words.  One could,  never-the
less, store a vocabulary of close to 1000 words in 2 K and perhaps write a
simple word game in 4 K of ROM.   Of course, 1000 words is a pretty  small
vocabulary and one would like to have a good many more words.

Perhaps a better compromise would be to plan on 8 K of ROM and then to use
6 K of  this for a  vocabulary of 3000  words, still leaving  2 K for  the
program.  One would still  have to limit the  allowed length of the  words
that could be  used to 8  characters in order  to be able  to specify  the
character position in 3 bits.

A sample 5-character-word  vocabulary excerpt is  shown below.  Note  that
the numbering could start with 0, thus allowing 8 letter words.  Also some
economy in  searching the  vocabulary may  be achieved  by storing  it  in
reverse word order,  and by using  the last 3  bits of each  byte for  the
number rather than the first 3 as shown.

    Characters (shown staggered)	    Word #   Total bits

1A	2B	3A	4-			1	4	
			4C	5K		2	6	
			4F	5T		3	8	
			4C	5E		4	10	
			4S	5H		5	12	
			4T	5E		6	14	
		3B	4Y			7	16	
			4O	5T		8	18	
		3E	4D			9	20	
			4T 			10	21	
		3H	4O	5R		11	24
		3I	4D	5E		12	27	
		3L	4E			13	29	
			4Y			14	30
		3O	4D	5E		15	33	
			4R	5T		16	35	
			4U	5T		17	37
			4V	5E		18	39	
		3U	4S	5E		19	42	
			4T	5-		20	44	
				5S		21	45	
	2C	3E	4-			22	48	
			4S	5-		23	50
		3H	4E	5-		24	53	
				5S		25	54
		3I	4D	5-		26	57	
				5S		27	58	
		3N	4E	5-		28	61	
				5S		29	62
		3O	4C	5K		30	63	
			4R	5N		31	65	
		3R	4E	5-		32	68	
				5S		33	69
			4I	5D		34	71	
		3T	4-			35	73
			4O	5R		36	75	
			4S			37	76	
	2D	3A	4G	5E		38	80	
			4P	5T		39	82	
		3D	4-			40	84	
			4A	5X		41	86	
			4E	5R		42	88	
			4L	5E		43	90	
			4S			44	91	
		3E	4P	5T		45	94
		3I	4T	5-		46	97	
		3M	4I	5T		47	100	
		3O	4-			48	102	
			4B	5E		49	104	
			4P	5T		50	106	
			4R	5E		51	108	
				5N		52	109	
		3U	4L	5T		53	112	
			4S	5T		54	114

Average	number	of	bytes	per	word	2.1

10,000 word vocabulary on SLOVAR [S,LES]
Text storage with data compression

Text storage in the Video-Brain can present a problem.  The size of
the available memory will usually be too small to permit the storage of the
desired amount of text without some sort of compression while the amount
of text to be stored is still too small to justify a very complicated text
compression scheme which would require an elaborate decoding program.

Some saving in space with ordinary text can be achieved without resorting
to a very complicated code if one is willing to forgo the use of upper and
lower case and if one limits the number of characters that are to be
stored..  One such code as discribed below will result in the storing of
approximately 1.7 characters per byte as compared with 1,33 for a packed
6-bit code. One would have to make a detailed study of the relative size of
the program required to use this scheme as compared to the size of the program
to do simple packing before one could be sure that this saving would be worth
while.

We will assume that one wants to use 26 letters, the digits 0 through 9
and 3 punctuation marks,  , . and ? and that we want the code to consist
of 4-bit "nibbles" which can be packed two to a byte.  It is assumed that 
there would be no need for a carriage return signal and that this function
would be handled automatically by padding with spaces to the end of a fixed
length line.

There would be three modes, a normal-letter mode, a temporary
alternate-letter mode, and a digit mode, with certain nibbles while in the
normal-letter mode and in the digit mode reserved as mode changing
signals.  The scheme as outlined could be extended to provide for yet
another mode, probably a temporary mode to allow for the inclusion of 16
additional but seldom used characters, if this seemed desirable.

When in the normal-letter mode, nibble 0 would stand for a space, nibbles
1 thru 13 would stand for the 13 most commonly used letters, with nibbles
of 14 and 15 reserved for mode changing signals.  Nibble 14 would result in
a temporary one-character change to the alternate-letter mode, with the
mode then reverting to the normal-letter mode.  Nibble 15 would result in
a change to the digit mode for all following nibbles.

When in the alternate-letter mode the nibbles 0 thru 12 would represent
the remaining letters with 13 thru 15 standing for the 3 punctuation
marks.  This mode would persist for only one character and the mode would
then revert to one of the other modes as determined by the signal that
called this temporary mode.

When in the digit mode, the nibbles 0 thru 9 would represent the digits 0
thru 9 with nibble 10 standing for a period or decimal mark.  These
nibbles would not result in any change from the digit mode.  Nibble 11
would cause a temporary change to the normal-letter mode, nibble 12 would
indicate a switch to the normal-letter mode, nibble 13 would indicate a
temporary shift to the alternate-letter mode with a return to the digit
mode, while nibble 14 would indicate a temporary shift to the
alternate-letter mode for one character and a mode change thereafter to
the normal-letter mode.  Nibble 15 is unassigned but it could be used to
invoke yet another temporary mode that could contain 16 desired but seldom
used characters.

Alternate scheme

Modified Huffman
Use a basic 4-bit code with 0 for a space, 15 for a continuation signal,
and 1 thru 14 for the most frequently used letters.  On this basis, and
using the below frequencies, 87.08% of the letters (and the space) would
each require 4 bits.  For alphabetical texts only and with no numbers or
punctuation, the rest of the letters would then require 8 bits.
This computes to an average of 4.4 bits per character (assuming 1/5
spaces).

Punctuation and the digits could be accomodated by yet another signal
signal.  This would raise the average number of bits slightly, perhaps to
4.6.

The net saving by all of this would hardly seem worth while except that the
unpacking would probably be simplier to accomplish than it would be using
a straight 5 or 6 bit code.


DON's figures
On a scale of 10000, the combined books tallied
A:815	E:1295	I:647	M:233	Q:9	U:274	Y:193
B:144	F:198	J:10	N:696	R:537	V:85	Z:3
C:200	G:216	K:93	O:740	S:570	W:279
D:515	H:772	L:405	P:130	T:930	X:11

Descending frequency: E T A H O N I S R D L W U M G C F Y B P K V X J Q Z
Penny matching

It is possible to write a simple program which will usually out-play a
person who choses heads or tails and then lets the program "guess" what
his choice had been.  For the scheme to work the result of each trial must
be reported to the program correctly and it then depends upon the fact
that a person simply cannot behave in a truly random fashion.

The only way that a person can hope to outguess the program is for him to
actually flip a coin or use some other random device to make his choice
for him and then, of course, he will fool the program only half the time.
Most people refuse to believe that a computer program can be this smart
and they feel intuitively that their chances are better if they make the
decisions.